1. Field of the Invention
The present invention relates to a packet switch and a packet switching method for switching packets between a plurality of ports.
2. Description of the Background Art
In recent years, there are considerable progresses in the field of data communications. Traditionally, the most representative communication network has been a telephone network, but the importance of a data communication network such as Internet is increasing rapidly due to the spread of PCs for business use and home use. Recently a technique for realizing telephone service on the data communication network has also been developed by taking advantages of low cost and high efficiency of the data communication network, and there is even a discussion of amalgamation of the telephone network into the data communication network.
Now, the data communication networks are mostly packet switching networks (which are to be construed as including ATM switching networks) that carry out communications of data to be transmitted to which information indicating a destination is attached, that is, packets (which are to be construed as including cells in ATM. As the traffic amount of the data communications increases, there is an increasing demand for a larger scale packet switch for switching these packets.
There are many propositions for a configuration of a packet switch, which can be largely classified into two types. One is a multiple stage switch type in which the number of ports can be made large, which is a rather old type, and the other is a single stage switch type in which the number of ports is small, which is a relatively new type.
The single stage switch type packet switches are often equipped with a congestion control mechanism in order to prevent a congested output port from affecting flows of packets destined to the other non-congested output ports. In contrast, the multiple stage switch type packet switches presuppose that the traffic characteristics (rate) are determined in advance, so that a severe congestion has not been taken into consideration in most of them. It appears that this is also largely due to the fact that it has been difficult to implement a mechanism for dealing with the congestion in the multiple stage switch type which presupposes the extension to the large number of ports, because the congestion occurs as a result of interplay between a plurality of input ports and a plurality of output ports.
In the Internet which is the most representative data communication network, a rate by which each user transfers packets is not determined in advance, so that the congestion can possibly occur anywhere at any time. For this reason, in designing an architecture of a packet switch, techniques for dealing with the congestion are equally important as techniques for realizing the large scale implementation. The techniques for dealing with the congestion include a technique for notifying a user so as to have the packet transfer rate lowered by the user when the congestion occurs within the packet switch, and a technique for preventing the occurred congestion from affecting flows of packets that are unrelated to that congestion.
In the following, such a conventional multiple stage switch type packet switch will be described briefly.
In the case of the multiple stage switch type packet switch, a large scale packet switch can be obtained by combining smaller switching elements in multiple stages (see Joseph Y. Hui: “Switching and Traffic Theory for Integrated Broadband Networks”, ISBN 0-7923-9061-X, Kluwer Academic Publishers, 1990, sections 5.5 and 6.3).
FIG. 1 shows an exemplary configuration of a multiple stage switch type packet switch of 27 inputs and 27 outputs obtained by combining switching elements 145 each having 3 inputs and 3 outputs.
A packet entered from an input port 121 is transferred from an input side transfer unit 102 via a switching unit 104 to a desired output side transfer unit 106, and outputted from there to an output port 161. This multiple stage switch type packet switch can be extended to a lager packet switch by increasing the number of switching elements and the number of stages. Also, when each switching element is replaced by a larger switching element of 8 inputs and 8 outputs, for instance, a large scale packet switch can be formed using lesser number of switching elements.
A well known configuration of the multiple stage switch type packet switch is that in which a random network and a routing network are connected in cascade connection. A random network 141 and a routing network 143 of FIG. 1 are coupling networks that are line symmetric with respect to each other. In each network, any input link can reach to arbitrary output link, through a unique route. By connecting the random network and the routing network in cascade connection, there are as many routes from a given input side transfer unit 102 to a given output side transfer unit 106 as the number of switching elements on a border between the random network and the routing network (nine in FIG. 1).
A packet outputted from the input side transfer unit 102 is transferred to a randomly selected link so as not to collide with other packets within the random network 141 and reaches to an input of the routing network 143. This random transfer is done for the purpose of distributing packets probabilistically to inputs (nine in FIG. 1) of the routing network 143. The packet is then transferred according to its destination within the routing network 143 and reaches to the output side transfer unit 106.
Inside the routing network 143, there is a possibility for a packet collision to occur as a result of having a plurality of packets simultaneously transferred towards one and the same output link of some switching element. If they are packets destined to the same output side transfer unit 106, they are bound to collide, and even if they are packets destined to different output side transfer units 106 they may still collide. In a packet switch in which each switching element does not have a queuing buffer, when the collision occurs, only one of these packets is transferred while the other one is immediately discarded. When a packet is discarded as a result of such a collision, the corresponding input side transfer unit 102 re-transmits the discarded packet.
In this way, even when a packet is discarded inside the switching unit 104, the input side transfer unit 102 keeps re-transmitting that packet until it is successfully transferred to the output side transfer unit 106. Consequently, the packet information will never be lost inside the switching unit 104. When viewed from outside of the packet switch, the packet is discarded only inside the input side transfer unit 102 and the output side transfer unit 106.
In the packet transfer control in such a multiple stage switch type packet switch, three types of congestion may occur, each of which will now be described. Here, for the sake of clarity of the explanation, it is assumed that the switching unit 104 has 4 inputs and 4 outputs obtained by combining switching elements of 2 inputs and 2 outputs each in 3 stages as shown in FIGS. 2 to 4.
Even in this small scale switching unit, the configuration is basically the same as FIG. 1 in that it has the random network 141 from the first stage switching element 145 up to the input of the second stage switching element, and the routing network 143 from the output of the second stage switching element up to the third switching element 145, so that the following description of the three types of congestion is applicable to the switching unit of FIG. 1 or even larger scale.
First, with reference to FIG. 2, the first type of congestion will be described.
In an example shown in FIG. 2, it is assumed that a packet destined to the output transfer unit [C] exists at the input side transfer unit [A], and a packet destined to the output side transfer unit [D] exists at the input side transfer unit [C]. In this case, an ideal packet switch should be able to transfer these two packets simultaneously as they have different destinations. However, in practice, there can be situations in which the random network 141 transfers these two packets (accidentally) to the lower side switching element 145 at the second stage of the switching unit 104, for example. When such a situation occurs, these two packets cannot reach to their respective destinations simultaneously. On the contrary, if these two packets are transferred separately to the upper side switching element and the lower side switching element at the second stage, this congestion could have been avoided. Such a congestion will be referred to as “inside routing network collision”.
There are several propositions for resolving the transfer performance degradation due to this inside routing network collision. For example, the known methods Include a method for connecting a random network in cascade connection as a front stage of the routing network so as to distribute packets such that the inside routing network collision will not be concentrated to a particular set of packets, and a method for increasing the packet transfer rate of the switching unit higher than that of the input port and the output port such that the apparent throughput from outside the packet switch will not be lowered even when packet re-transmissions take place due to this congestion. By devising the switch architecture in this way so that the congestion will not occur continually, it is possible to conceal the influence of this congestion from outside the switch.
Next, with reference to FIG. 3, the second type of congestion will be described.
In an example shown in FIG. 3, it is assumed that packets destined to the same output side transfer unit [C] exist at two input side transfer units [A] and [C]. These two packets are bound to collide before they reach to the output side transfer unit [C] regardless of the routes by which they are transferred inside the random network 145. Such a congestion will be referred to as “output side transfer unit input congestion”.
This congestion occurs basically when packets having the same destination are concentrated continually. For example, in FIG. 3, if there is a flow of packets destined to the output side transfer unit [D] from the input side transfer unit [B] in addition, the flow of the packets destined to the output side transfer unit [D] would be degraded due to an influence of the continual transfer of excessive packets destined to the output side transfer unit [C].
In the packet switch such as the conventional multiple stage switch type one, there are many output side transfer units so that a method for appropriately dealing with this congestion has been an unresolved problem. This is because, when there are many output side transfer units, it has been difficult to collect information as to which output side transfer unit is crowded and which output side transfer unit is not, all at once.
Next, with reference to FIG. 4, the third type of congestion will be described.
This congestion occurs when the rate of the output port of the output side transfer unit ([C] in an example of FIG. 4) is slower than the arrival rate of packets destined to that port. This congestion will be referred to as “inside output side transfer unit congestion”. In an example shown in FIG. 4, when the output side transfer unit [C] is congested, it is actually meaningless for the input side transfer unit [A] to transfer packets destined to the output side transfer unit [C] unnecessarily frequently, and it suffices to transfer at about the rate of the output port of the output side transfer unit [C].
However, the conventional packet switch could have transferred excessively many packets to the same output port, and this in turn induces the first type congestion (inside routing network collision) and the second type congestion (output side transfer unit input congestion) described above. This completes the description of the three types of congestion.
As described, the conventional multiple stage switch type packet switch has an advantage in that it can be formed in a large scale by combining switching elements, but there has been no satisfactory method for dealing with the severe congestion. In other words, there has been a possibility for having a large number of packets destined to the congested port transferred within the switching unit. These are wasteful transfers for which the possibility of being discarded within the switching unit is high. The transfers in excess of the transfer rate of the output port is actually meaningless, and it could cause a situation in which a large number of packets that are transferred in excess are discarded within the switching unit and re-transmitted repeatedly. In such a situation, even packets destined to non-congested ports may collide with packets destined to the congested port within the switching unit such that the discarding and the re-transmission are repeated and the flow is degraded. This is a drawback that can eventually lower the packet transfer efficiency of the entire packet switch considerably.
Thus there has been a demand for the congestion control in the multiple stage switch type packet switch in which the number of ports can be made large, for the purpose of application to the Internet or the like in which the traffic is increasing rapidly.